package com.lyf.alg.practice.huawei.stack;

import java.util.Scanner;
import java.util.Stack;

/**
 * @AUTHOR LYF
 * @DATE 2022/5/24
 * @VERSION 1.0
 * @DESC
 * 火车进站
 */
public class Hj77 {
    public static void main(String[]args){
        Scanner s = new Scanner(System.in);
        int k = s.nextInt();
        int[]arr =new int[k];
        for(int i=0;i<k;i++){
            arr[i]=s.nextInt();
        }
        Stack<Integer> stack = new Stack<>();
        recursion(stack,0,arr);
    }

    static Stack tmp = new Stack<>();
    static void recursion(Stack stack,int ptr,int[]arr){
        if(stack.isEmpty()&&ptr==arr.length){
            // sout
            String rs = "";
            while(!tmp.isEmpty()){
                rs = tmp.pop()+" "+rs;
            }
            System.out.println(rs);
            return;// 终止
        }

        if(stack.isEmpty()){
            // 只能进栈
            stack.push(arr[ptr++]);
            recursion(stack,ptr,arr);
        }else if(ptr==arr.length){
            // 只能出栈
            tmp.push(stack.pop());
            recursion(stack,ptr,arr);
        }else{
            // 出栈
            if(!stack.isEmpty()){
                tmp.push(stack.pop());
                recursion(stack,ptr,arr);
                // 回退
                stack.push(arr[ptr-1]);
                tmp.pop();
            }
            // 另外一种情况
            stack.push(arr[ptr++]);
            recursion(stack,ptr,arr);
        }


    }

}
